As is well known in the art, one of the techniques for rendering an image of an object on a screen (such as, for example, a computer monitor) involves defining a piece-wise approximation of surface contours of the object using a “mesh” composed of a number of (nominally planar) polygons. Typically, all of the polygons within the mesh will be geometrically similar (rectangular or triangular, for example) but their size and shape will vary. Because the vertices of each polygon can be explicitly defined, the mesh can be readily mapped to appropriate pixel coordinates of the screen. A surface texture (including, inter alia, color and shading information) can then be applied to each polygon of the mesh to fully render the image.
As is also well known in the art, the level of detail in the rendered image is directly related to the size of the polygons within the mesh. Thus, for example, a large number of small polygons are used where a high level of surface detail is required, whereas a smaller number of large polygons can be used where less detail is needed. However, the amount of processing resources required to render an image is directly related to the number of polygons within the mesh. As a result, rendering a highly detailed image (consisting of a large number of polygons) of an object requires more processor resources, and thus typically takes longer, than rendering an image of the same object with less detail. Current graphics processing systems are typically capable of rendering millions of polygons per second. However, since smooth animation requires that an image be refreshed at a rate of at least 30 frames per second, a compromise between animation performance and rendering detail must normally be found.
Frequently, objects (such as, for example, characters in a video game) are generated using a so-called “base mesh” composed of a minimum number of large polygons, and so provides a minimum level of rendering detail. The polygons forming the base mesh are normally referred to as “primitives”. These primitives are normally selected to enable the position and orientation of the object within a scene to be rapidly (and unambiguously) defined, and thereby facilitate appropriate scaling and animation of the object. In cases where a higher level of detail is required, additional polygons can be defined within each primitive, as needed.
The process of defining polygons within a primitive is referred to as “tessellation”, and the number of polygons defined within a primitive is given by the “tessellation rate”. Formally, the tessellation rate is the number of segments into which an edge of the primitive is divided by the vertices of the polygons defined within the primitive. Thus, for example, a primitive has (by definition) a tessellation rate of 1. If one or more polygons are then defined within the primitive, such that one new vertex lies on each edge of the primitive (thereby dividing each edge into two segments), then the tessellation rate will be 2. Similarly, If further polygons are then defined within the primitive, such that two vertices lie on each edge of the primitive (thereby dividing each edge into three segments), then the tessellation rate will be 3. As may be appreciated, since the tessellation rate (or value) is based on the number of segments into which an edge of the primitive is divided, the tessellation rate can be defined on a “per-edge” basis. In principle, this means that different edges of a primitive may have the same, or different, tessellation values.
Traditionally, base meshes are tessellated uniformly, meaning that all of the edges of each primitive have the same tessellation value. By extension, since adjacent primitives within the mesh share a common edge, all edges inside of the base mesh will necessarily have the same tessellation value. This implies that the same level of detail will be obtained throughout an image being rendered. As may be appreciated, uniform tessellation tends to yield a highly inefficient utilization of processor resources.
For example, portions of an object lying closer to the “camera position” (that is, the point from which a scene is observed) should be rendered with a high level of detail, while portions of the same object lying farther from the camera position can satisfactorily be rendered with less detail. When the entire object is rendered with uniform tessellation, the tessellation rate must be selected to provide the high-detail needed for portions close to the camera position. This implies that significant processing resources will be utilized defining and rendering unnecessary polygons in those portions of the object lying farther away from the camera position.
Another problem with uniform tessellation is that primitives facing away from the camera (which are inherently invisible) will be tessellated at the same rate as the visible primitives. This incurs a further waste of processing resources. A similar problem exists for primitives that are oriented at an angle near the “line of sight” from the camera position. These primitives typically denote the silhouette of the object, so higher tessellation rates would be beneficial. On the other hand, primitives fully facing the camera can be rendered with lower tessellation, because the required level of detail can frequently be provided using less computationally intensive methods.
Improved efficiency of utilization of processor resources can be obtained by the use of non-uniform tessellation in each primitive. Traditionally, this is accomplished by assigning a different tessellation rate to each edge of a primitive.
However, non-uniform tessellation suffers the problem that “cracks” can form along a shared edge between adjacent primitives with differing tessellation rates. In particular, a crack can occur at a “T-junction”, which is formed when a vertex lying on a shared edge between a pair of primitives is connected to a polygon defined in only one of the involved primitives. This commonly occurs under two scenarios. A first scenario is a case in which edge tessellation rates are assigned with reference to each primitive. In the case of a shared edge, it is therefore possible to have a situation in which the edge tessellation rate relative to one primitive is different from that assigned relative to the other primitive sharing the same edge. A second scenario is a situation in which the edge tessellation rate is assigned without reference to any primitives (and thus will be the same of both primitives) but the respective vertices for polygons defined within each primitive are calculated in the local coordinate system of each primitive. In either scenario, rounding errors and misalignment between the local coordinate systems of the involved primitives can result in differences between the coordinates of vertices (calculated relative to each primitive) that should overlay one another, which causes a gap (or crack) to open between the two primitives. In a displayed image, such a crack can be made visible when an object “A” should obstruct the viewer's view of an object “B”. A crack in object A can result in object B being at least partially visible through object A, which is clearly undesirable.
One known method of dealing with cracks is to use a post-processing method to identify and fill cracks before rendering the image on the screen. However, this solution consumes substantial processing resources, and thus at least partially negates the benefits of adopting a non-uniform tessellation regime.
In an animated scene, an object may move between the background and foreground of the scene, as well as across the field of view. As may be appreciated, as an object moves toward the camera position, the level of detail should progressively increase. Conversely, as the object moves away from the camera position, the level of detail should progressively decrease. Similarly, the level of detail should be higher for objects lying in the central portion of the field of view, and progressively diminish toward the edge of the frame. Preferably, these changes in the level of detail should be smooth, which requires that topological and geometric continuity must be preserved as the tessellation rate changes. If different schemes (i.e., the number and/or arrangement of polygons within a primitive) are implemented for different levels of tessellation, then continuity must be preserved during transitions between schemes. Topological and geometric discontinuities can be seen in a rendered image in the form of surface features that appear or disappear instantly, rather than gradually emerging (and enlarging) or fading out (and growing smaller). The sudden appearance and disappearance of features is referred to as “popping”, and is clearly undesirable. However, such popping is commonly encountered in conventional systems, because changes in the tessellation rate unavoidably involve changing the tessellation scheme, as at least some large polygons are replaced by two or more smaller polygons.
Accordingly, a method of tessellating a primitive which permits efficient utilization of processing resources, prevents cracking, and ensures topological and geometric continuity (and thereby prevents popping) remains highly desirable.